package com.jz.algorithm.LinkedList;

import java.util.*;

/**
 * @ClassName : LinkedList
 * @Description : 链表
 * @Author : becky
 * @Date: 2021/8/28  10:27
 */
public class MyLinkedList<T> {
    private Node<T> head;
    private Node<T> last;
    private int length;

    public MyLinkedList() {
        head = new Node<T>();
    }

    public MyLinkedList(Node<T> head) {
        this.head = head;
    }

    public Node<T> addLast(T value) {
        Node<T> tNode = new Node<T>();
        Node<T> tNode1 = new Node<T>(value, null);
        tNode = head;
        while (tNode.next != null) {
            tNode = tNode.next;
        }
        tNode.next = tNode1;
        last = tNode1;
        length++;
        return tNode1;
    }

    public Node<T> addLast(Node node) {
        Node<T> tNode = new Node<T>();

        tNode = head;
        while (tNode.next != null) {
            tNode = tNode.next;
        }
        tNode.next = node;
        last = node;
        length++;
        return node;
    }

    public T addlValueAfter(T newValue, T destValue) {
        Node<T> cur = head;
        Node<T> tNode = new Node<T>(newValue, null);

        while (!cur.next.data.equals(destValue)) {
            cur = cur.next;
        }
        if (cur.next.next == null) {
            cur.next.next = tNode;
            last = tNode;
        } else {
            Node<T> node = cur.next.next;
            cur.next.next = tNode;
            tNode.next = node;
        }
        return newValue;


    }

    public boolean isEmpty() {
        return length == 0;
    }
    public int[] intersection(int[] nums1, int[] nums2) {
        HashSet set=new HashSet<>();
        ArrayList<Integer> objects1 = new ArrayList<>();
        int index=1;

        for(int i=0;i<nums1.length;i++){
            set.add(nums1[i]);
        }
        for(int j=0;j<nums2.length;j++){
            if(set.contains(nums2[j])){

                objects1.add(nums2[j]);
                set.remove(nums2[j]);
            }
        }
        int [] a=new int [objects1.size()];

        for(int j=0;j<objects1.size();j++){
            a[j]=objects1.get(j);
        }
        return a;

    }

    public static void main(String[] args) {
        HashSet<Object> objects = new HashSet<>();
        HashMap<Integer, Integer> objectObjectHashMap = new HashMap<>();




        for (int i = 0; i < 7; i++) {
            
        }
        MyLinkedList<String> stringLinkedList = new MyLinkedList<String>();
        MyLinkedList<String> stringLinkedList1 = new MyLinkedList<String>();


        String s="sssss";



        stringLinkedList.addLast("1");
        stringLinkedList.addLast("2");
        stringLinkedList.addLast("3");
        stringLinkedList.addLast("4");

        Node node = new Node<String>("5", null);
        Node node6 = new Node<String>("6", null);
        Node node7 = new Node<String>("7", null);
        Node node8 = new Node<String>("8", null);

        stringLinkedList.addLast(node);
        stringLinkedList.addLast(node6);
        stringLinkedList.addLast(node7);
        stringLinkedList.addLast(node8);

        stringLinkedList1.addLast(node);


        Node intersectionNode = getIntersectionNode(stringLinkedList.head, stringLinkedList1.head);

//        Node<String> head = stringLinkedList.head;
//        while (head.next != null) {
//            System.out.println(head.next.data);
//            head = head.next;
//        }
        Node<String> head1 = stringLinkedList.head;
        //reverseLikedList(head1);
        //  reverseLinkedListByRecurrence(head1.next);
        //removeNthFromEnd(head1.next,2);
        // swapPairs(head1);
        System.out.println("翻转后------------------------");
        Node<String> head2 = stringLinkedList.head;
        while (head2.next != null) {
            System.out.println(head2.next.data);
            head2 = head2.next;
        }
    }


    /**
     * @return
     * @throws
     * @Param : head1为头节点
     * @Description :  链表的反转
     * @Author : Jz
     * @Date :   2021/08/30 09:31
     */
    private static void reverseLikedList(Node<String> head1) {
        if (head1.next == null) {
            System.out.println("此链表为空");
            return;
        }
        Node<String> first = head1.next;
        Node<String> pre = null;
        Node<String> next = null;
        while (first != null) {
            next = first.next;
            first.next = pre;
            pre = first;
            first = next;
        }
        head1.next = pre;


    }

    //翻转链表

    public static Node<String> reverseLinkedList(Node<String> head) {

        Node<String> pre = null;
        Node<String> cur = head.next;
        Node<String> temp = null;

        while (cur != null) {

            temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;

        }
        head.next = pre;
        return pre;

    }


    /**
     * @return 头节点
     * @throws null
     * @Param : 头节点
     * @Description : 通过递归方式去反转链表
     * @Author : Jz
     * @Date :   2018/08/30
     */
    public static Node<String> reverseLinkedListByRecurrence(Node<String> head) {
        if (head == null || head.next == null) {
            return head;
        }
        Node<String> cur = reverseLinkedListByRecurrence(head.next);
        head.next.next = head;
        head.next = null;
        return cur;
    }


    /**
     * @Methodname swapPairs
     * @Description 给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
     * @Date 2021/11/9 14:30
     * @Author Jz
     * @Return 节点值
     * @Param 头节点
     */
    public static Node swapPairs(Node head) {
        if (head == null) {
            return null;
        }


        Node temp = head.next;
        Node pre = head.next.next;
        while (temp != null && temp.next != null) {
            Node p = temp;
            Node q = temp.next;
            temp = q.next;
            p.next = q.next;
            q.next = p;

        }

        return pre;


    }


    /**
     * @return 返回被删除的第n个节点
     * @throws null
     * @Param : n 删除倒数第n个节点
     * @Description :  删除倒数第n个节点
     * @Author : Jz
     * @Date :   2021/08/31
     */

    public static Node<String> deleteEndNode(int n, MyLinkedList myLinkedList) {
        int length = myLinkedList.length;
        Node first = myLinkedList.head.next;
        Node pre = null;

        for (int i = 1; i < length - n; i++) {
            pre = first;
            first = first.next;
        }
        pre.next = first.next;
        return myLinkedList.head;
    }

    public static Node<String> removeNthFromEnd(Node<String> head, int n) {
        int i = 0;
        Node p = head;
        Node q = head;
        while (p != null) {
            p = p.next;
            if (i >= n) {
                q = q.next;
            }
            i++;
        }
        if (i <= n) {
            head = q.next;
        } else {
            q.next = q.next.next;
        }
        return head;


    }

    public static Node  getIntersectionNode(Node headA, Node headB) {
        int lengthA = getLinkedListLength(headA);
        int lengthB = getLinkedListLength(headB);
        if (lengthA > lengthB) {

            for (int i = 0; i < lengthA; i++) {
                headA = headA.next;
                if (i > lengthA - lengthB) {
                    headB = headB.next;
                }
                if (headA == headB.next) {
                    return headA;
                }
            }

        } else {
            for (int i = 0; i < lengthB; i++) {
                headB = headB.next;
                if (i > lengthB - lengthA) {
                    headA = headA.next;
                }
                if (headA.next == headB) {
                    return headB;
                }
            }

        }
        return null;


    }

    private static int getLinkedListLength(Node head) {
        int count = 0;
        while (head != null && head.next != null) {
            head = head.next;
            count++;
        }
        return count;
    }

}
